package tree;

public class BinaryTree<Key extends Comparable<Key>, Value> {
    private class Node{

        public Key key;

        private Value value;

        public Node left;
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    //根节点
    private Node root;
    //元素个数
    private int N;

    //向树中插入键值对
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    //给指定树x上，添加键一个键值对，并返回添加后的新树
    private Node put(Node x, Key key, Value value) {
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }
        int cmp = key.compareTo((Key) x.key);
        if (cmp == 0) {
            x.value = value;
        } else if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else {
            x.left = put(x.left, key, value);
        }
        return x;
    }

    //根据key，从树中找出对应的值
    public Value get(Key key) {
        return get(root, key);
    }

    //从指定的树x中，找出key对应的值
    public Value get(Node x, Key key) {
        int cmp = key.compareTo( x.key);
        if (cmp == 0) {
            return x.value;
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return get(x.left, key);
        }
    }

    //根据key，删除树中对应的键值对
    public void delete(Key key) {
        delete(root, key);
    }

    //删除指定树x上的键为key的键值对，并返回删除后的新树
    private Node delete(Node x, Key key) {
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {
            return x = null;

        } else if (cmp > 0) {
            return delete(x.right, key);
        } else {
            return delete(x.left, key);
        }
    }

    //获取树中元素的个数
    public int size() {
        return N;
    }


}
